#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>

using namespace std;

// 全排列
class Solution
{
public:
    vector<vector<int>> ans;
    vector<int> path;
    bool check[7];
    vector<vector<int>> permute(vector<int> &nums)
    {
        dfs(nums);
        return ans;
    }
    void dfs(vector<int> &nums)
    {
        if (path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

// 用栈实现队列
class MyQueue
{
public:
    MyQueue()
    {
    }

    void push(int x)
    {
        push_st.push(x);
    }

    void move()
    {
        if (pop_st.empty())
        {
            while (push_st.size())
            {
                pop_st.push(push_st.top());
                push_st.pop();
            }
        }
    }
    int pop()
    {
        move();
        int ans = pop_st.top();
        pop_st.pop();
        return ans;
    }

    int peek()
    {
        move();
        return pop_st.top();
    }

    bool empty()
    {
        return push_st.empty() && pop_st.empty();
    }

private:
    stack<int> push_st;
    stack<int> pop_st;
};

// 用队列实现栈
// 保持一个队列为空,出队列的时候将不为空的队列中出多列n-1个
// 剩余的即为栈顶的元素
class MyStack
{
public:
    MyStack()
    {
    }

    void push(int x)
    {
        if (q1.empty())
        {
            q2.push(x);
        }
        else
        {
            q1.push(x);
        }
    }

    int pop()
    {
        if (q1.empty())
        {
            while (q2.size() > 1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            int ans = q2.front();
            q2.pop();
            return ans;
        }
        else
        {
            while (q1.size() > 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            int ans = q1.front();
            q1.pop();
            return ans;
        }
    }

    int top()
    {
        if (q1.empty())
            return q2.back();
        else
            return q1.back();
    }

    bool empty()
    {
        return q1.empty() && q2.empty();
    }

private:
    queue<int> q1;
    queue<int> q2;
};

// 二叉树层序遍历
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        if (root == nullptr)
            return {};
        vector<vector<int>> ans;
        queue<TreeNode *> q;
        q.push(root);
        while (q.size())
        {
            int size = q.size();
            vector<int> path;
            while (size--)
            {
                TreeNode *root = q.front();
                q.pop();
                if (root->left)
                    q.push(root->left);
                if (root->right)
                    q.push(root->right);
                path.push_back(root->val);
            }
            ans.push_back(path);
        }

        return ans;
    }
};

// 合并两个有序链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *newhead = new ListNode;
        ListNode *tail = newhead;
        while (list1 && list2)
        {
            if (list1->val <= list2->val)
            {
                tail->next = list1;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        if (list1)
            tail->next = list1;
        if (list2)
            tail->next = list2;

        ListNode *ans = newhead->next;
        delete newhead;
        return ans;
    }
};

// 在排序数组中查找元素的第一个和最后一个位置
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        auto left = std::lower_bound(nums.begin(), nums.end(), target);
        if (left == nums.end() || *left != target)
        {
            return {-1, -1};
        }
        auto right = std::upper_bound(nums.begin(), nums.end(), target) - 1;
        return {static_cast<int>(distance(nums.begin(), left)), static_cast<int>(distance(nums.begin(), right))};
    }
};

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        if (nums.empty())
            return {-1, -1};
        int begin = 0, left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        if (nums[left] != target)
            return {-1, -1};
        begin = left;
        right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        return {begin, right};
    }
};